Service Placement and Request Sched

• Service Placement and Request Scheduling for Data-Intensive Applications in

• 一、介绍
  • 1.1 这篇文章讲的什么？
    • 并不是总选择最近的基站就最好，可以通过标准化计划创建一个开放的边缘计算环境，使得地理区域内的边缘云形成一个共享资源池
    • 有一些任务中（机器学习、关系数据库），数据大小比较大，同时一系列请求都基于这个数据，我们还要考虑这类任务需要的存储资源和网络带宽。
    • 在上述任务中，边缘计算资源分配问题变为两个子问题：服务放置（每个服务器部署什么服务）和请求调度（每一个请求分别在哪里处理）。
    • 目前的计算方式中，上述两个任务是同时变化的，因此会出现任务请求频繁换位置的同时，服务放置也不断换位置。
    • 本文研究的是这种需要存储的问题，在计算中应将其任务部署位置和计算位置分开进行决策，服务放置变化较慢，取决于用户位置，请求的调度变化较快，取决于该请求预期消耗的计算时间
  • 1.2 之前文章的工作？
    • 有许多研究是关于负载调度的问题，有些任务在服务器上多次跳动，效率比在最近的服务器要高。但这些研究都假设一个资源单元只能被一个工作负载使用，实际上存储资源可被多个作业使用。
    • 另一些研究考虑了存储资源的共享，基于预测或者是历史数据，将容量保持在缓存容量限制之内。但是其只考虑储存，没有考虑带宽和 cpu
    • 有一篇研究考虑了资源放置和请求分配的问题，但是它假设带宽、存储资源、计算资源都是由边缘云决定的。但本文认为计带宽由边缘云决定，其他资源由边缘云选择处理的请求决定。
• 二、公式化模型
  • 2.1 我们的模型考量？
    • 本文建立一个混合整数线性规划 milp 模型
    • 如果用户需要 l 服务，他首先提交请求到自己所处的边缘云 n，之后边缘云 n 通过路由传递给边缘云 m，通常 m 与 n 不同。
    • 我们考虑用户与 n 之间的通讯成本、m 的计算成本。对于云 m 来说，其与 n 之间的通讯也会消耗 m 的通讯资源，但是我们不考虑。（as back-haul links usually have much higher bandwidth than access links）
  • 2.2 数学模型？
    • 1.服务放置的优化模型（影子调度）
      • 每一帧要配置云中的服务。其中 l，n 请求在 m 上被满足的概率为影子调度变量，最终不作为调度的结果。仅有是否在 n 上放置服务为求解的最终变量。
      • 目标 1a：对每一些 l，n 请求，对在所有云 m 上被满足的概率求和，这个概率和乘这些 l，n 请求的数量，最后对 l 和 n 求和.
      • 约束 1b：对于每一个 l，n，m，请求 l，n 在 m 上被满足的概率，对 m 求和，小于 1
      • 约束 1c：m 上是否放置 l 服务乘 l 服务消耗的空间，对于 l 求和，小于 m 的储存空间
      • 约束 1d：对于一些 l，n 请求，对在所有云 m 上被满足的概率求和，这个概率乘以这些 l，n 请求的数量，乘以 l 请求传输消耗的通信资源，对于所有 l 求和，小于 n 上的消耗资源。
      • 约束 1e：对于一些 l，n 请求，请求的数量乘以请求在 m 上被满足的概率对 n 求和，乘以请求 l 消耗的计算资源，对 l 求和，小于 m 上的计算资源。
      • 约束 1f：对于 ln 请求，l 是否被放置在 m 上，乘以 ln 请求能否被 m 处理，大于 ln 请求在 m 被满足的概率。
      • 约束 1g：对于 ln 请求，l 是否被放置在 n 上，乘以 l 放置 到 n 上的消耗，对 l 和 n 求和，小于每一帧最大的服务放置消耗
      • 约束 1h：一些范围
      • 模型已知：ln 请求的数量、l 服务放置的消耗、
      • 模型未知：ln 请求在 m 被满足的概率、l 是否被放置在 n
    • 2.软资源约束下的请求调度
      • 那么就和上述服务配置的优化差不多了。
    • 3.硬资源约束下的请求调度
      • 相当于把问题 1.中的请求出现次数乘满足概率换成了请求被满足的次数。
    • 4.讨论：正是因为每一帧开始无法知道本帧确切需求，因此无法硬约束，因此对影子调度问题用软约束。
• 三、复杂度分析
  • 服务放置属于混合整数线性规划 MILP、软需求调度属于线性规划 LP、硬需求调度属于整数线性规划 ILP
  • 服务放置的复杂度？
  • 问题与 SAP 问题类似，即考虑在一定约束下将物品装到包中，可以对于专用和非专用资源建模。但是 sap 要求一个需求只能在一个边缘云上消耗资源，因为每个边缘云对于处理请求的限制是不同的，因此此问题并非 SAP 问题。
• 四、算法
• 五、扩展到多帧优化
• 六、表现评估